package heapSort;

public class HeapSort{

	public static void main(String[] args) {
		int[] a = {3,5,8,1,6,2,0,7,4,9,-1,2};
		heapSort(a);
		printArray(a);
	}
	
	private static void heapSort(int[] a) {
		/*构建初始堆，找到最后一个非叶子节点，逐个调整，满足大顶堆*/
		int lastIndex = (a.length-1)/2;//最后一个非叶子节点的下标
		for (;lastIndex>=0;lastIndex--) {
			adjestHeap(a,lastIndex,a.length-1);
		}
		/*将堆顶元素放到数组的最后，再次调整剩下的元素,堆的删除操作*/
		for (int i=a.length-1; i>=0; i--) {
			swap(a, 0, i);
			adjestHeap(a, 0, i-1);
		}
	}
	/**
	 * 调整堆操作
	 * @param a 数组
	 * @param root 当前根节点 下标
	 * @param i 范围下标
	 */
	private static void adjestHeap(int[] a, int root, int i) {
		int leftChild = 2*root+1;
		int rightChild = 2*root+2;
		int childmax = 0;//保存两个孩子的最大值的下标
		if (leftChild > i) { //退出递归条件
			return;
		}
		if (rightChild > i) {
			childmax = leftChild;
		} else {
			if (a[leftChild]<a[rightChild])
				childmax = rightChild;
			else
				childmax = leftChild;
		}
		if (a[childmax] > a[root]) {
			swap(a, childmax, root);
		}
		adjestHeap(a, childmax, i);//递推地调整下去
	}

	/**
	 * 打印输出数组a到控制台
	 * @param a
	 */
	private static void printArray(int[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+"\t");
		}
	}
	/**
	 * 交换数组中两个位置的值
	 * @param a
	 * @param i
	 * @param index
	 */
	private static void swap(int[] a, int i, int index) {
		int temp = 0;
		temp = a[i];
		a[i] = a[index];
		a[index] = temp;
	}
	

}
